//Given an array of intervals where intervals[i] = [starti, endi], merge all 
//overlapping intervals, and return an array of the non-overlapping intervals that 
//cover all the intervals in the input. 
//
// 
// Example 1: 
//
// 
//Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
//Output: [[1,6],[8,10],[15,18]]
//Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
// 
//
// Example 2: 
//
// 
//Input: intervals = [[1,4],[4,5]]
//Output: [[1,5]]
//Explanation: Intervals [1,4] and [4,5] are considered overlapping.
// 
//
// 
// Constraints: 
//
// 
// 1 <= intervals.length <= 10⁴ 
// intervals[i].length == 2 
// 0 <= starti <= endi <= 10⁴ 
// 
// Related Topics Array Sorting 👍 10765 👎 460


package leetcode.editor.en;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class _56_MergeIntervals {
    public static void main(String[] args) {
        Solution solution = new _56_MergeIntervals().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] merge(int[][] intervals) {
            Arrays.sort(intervals, Comparator.comparingInt(d->d[0]));
            int idx = -1;
            int[][] res = new int[intervals.length][2];
            for (int[] interval : intervals) {
                if (idx == -1 || interval[0] > res[idx][1]){
                    res[++idx] = interval;
                }else {
                    res[idx][1] = Math.max(interval[1], res[idx][1]);
                }
            }
            return Arrays.copyOf(res, idx+1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}